package AVLtree;

import RBTree.RBTree;

import java.util.Arrays;
import java.util.List;
import java.util.Random;

class textRBTree{
    public static void main(String[] args) {
        compareTime();
    }

    //多次插入时间的比较
    private static void compareTime() {
        int[] textArr = new int[100_000_000];
        Random random = new Random();
        for (int i = 0; i < textArr.length; i++) {
            textArr[i] = random.nextInt(100_000_000);
        }
        AVLTime(textArr);
        RBTime(textArr);

    }

    private static void RBTime(int[] textArr) {
        RBTree rbTree = new RBTree();
        Long TimeS = System.currentTimeMillis();
        for (int i = 0; i < textArr.length; i++) {
            rbTree.push(textArr[i]);
        }
        Long TimeE = System.currentTimeMillis();
        System.out.println(" RBTree所用时间" + (TimeE - TimeS));
        System.out.println(rbTree.IsBlackEqual(rbTree.root));
    }

    private static void AVLTime(int[] textArr) {
        AVLtree avLtree = new AVLtree();
        Long TimeS = System.currentTimeMillis();
        for (int i = 0; i < textArr.length; i++) {
            avLtree.push(textArr[i]);
        }
        Long TimeE = System.currentTimeMillis();
        System.out.println(" AVLTree所用时间" + (TimeE - TimeS));
    }

    public static void main9(String[] args) {
        Random random = new Random();
        RBTree hh = new RBTree();
        for (int i = 0; i < 19; i++) {
            int r = random.nextInt(100);
            hh.push(r);
        }
        System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));

        hh.inOrder(hh.root);
        System.out.println();
        System.out.println(hh.isUP());
        System.out.println(hh.IsBlackEqual(hh.root));
    }
    public static void main8(String[] args) {
        Random random = new Random();
        RBTree hh = new RBTree();
        AVLtree hhh = new AVLtree();
        //large
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 20980457; j++) {
                int r = random.nextInt(1002389);
                hh.push(r);
//                hhh.push(r);
            }
            System.out.println("创建完成");
            System.out.println(hh.isUP());
            System.out.println(hh.IsBlackEqual(hh.root));
            hh.arr.clear();
//            hh.inOrder(hh.root);
//            System.out.println("AVL height");
//            System.out.println(hhh.getHeight(hhh.root));

//            System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
//            System.out.println("RBTREE height");
//            System.out.println(hh.getHeight(hh.root));
        }
    }
    public static void main7(String[] args) {
        Random random = new Random();
        //插入
        RBTree hh = new RBTree();
        AVLtree hhh = new AVLtree();

//        hh.push(1);
        for (int i = 0; i < 10; i++) {
            int r = random.nextInt(100);
//            hh.push(i);//左旋
//            hh.push(10 - i);//右旋
            hh.push(r);
            hhh.push(r);
        }
            System.out.println("RBTREE");
            System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));

            System.out.println("AVLTREE");
            System.out.println(Arrays.toString(new List[]{hhh.levelOrder(hhh.root)}));

            System.out.println("RBTREE height");
            System.out.println(hh.getHeight(hh.root));

            System.out.println("AVL height");
            System.out.println(hhh.getHeight(hhh.root));


    }
}
public class text {


    public static void main(String[] args) throws findError {
        //contain text
        AVLtree hh = new AVLtree();
        for (int i = 0; i < 10; i++) {
            hh.push(i);
        }
//        System.out.println(hh.contain(90));
        System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
        //del
        for (int i = 0; i < 10; i++) {
            hh.del(i);
            System.out.println(i);
            System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
        }
        hh.del(1);
    }

    public static void main5(String[] args) {
        //重复去重测试
        AVLtree hh = new AVLtree();
        hh.push(1);
        hh.push(2);
        hh.push(3);
        hh.push(4);
        System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
        hh.push(1);
        hh.push(2);
        hh.push(3);
        hh.push(4);
        hh.push(5);
        hh.push(1);
        hh.push(2);
        hh.push(3);
        hh.push(4);
        hh.push(5);
        System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
    }

    public static void main6(String[] args) {
        //大量测试
        Random random = new Random();
        for (int j = 0; j < 1000; j++) {
            AVLtree hh = new AVLtree();
            for (int i = 0; i < 2000000; i++) {
                int a = random.nextInt(0, 2000000);
                hh.push(a);
            }
            System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
            System.out.println(hh.getHeight(hh.root));
        }
    }

    public static void main2(String[] args) {
        //左右双旋
        AVLtree hh = new AVLtree();
        int[] text = {60, 30, 70, 20, 40, 50};//左右双旋
        int[] text1 = {30, 20, 90, 60, 100, 50, 70, 80};//左右双旋

        for (int val : text1) {
            hh.push(val);
            System.out.println(Arrays.toString(new List[]{hh.levelOrder(hh.root)}));
        }
    }

    public static void main1(String[] args) {
        //验证左 右单旋
        AVLtree t = new AVLtree();
        for (int i = 0; i < 10; i++) {
            System.out.println(t.push(i));//左旋
//            System.out.println(t.push(9-i));//右旋
            List[] tmp = {t.levelOrder(t.root)};
            System.out.println(Arrays.toString(tmp));
        }
    }
}
